import sun.reflect.generics.tree.Tree;

import java.util.Stack;

public class Practice2 {

//    236. 二叉树的最近公共祖先(经典例题)
//    给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
//    最近公共祖先的定义为：“对于有根树 T 的两个（节点） p、q，最近公共祖先表示为一个节点 x，
//    满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
//    提示
//      树中节点数目在范围 [2, 105] 内。
//      -109 <= Node.val <= 109
//      所有 Node.val 互不相同 。
//      p != q  //值都不相同
//      p 和 q 均存在于给定的二叉树中。
//
//      思路一：
//    如果给定的树是一颗二叉搜索树
//      定义：
//      中序遍历的大小是有序的
//      根节点的左树  都比根小
//      根节点的右树  都比根大
//
//      1. root== p || root == q
//      此时的最近公共祖先是root
//      2、p.val < root.val && q.val < root.val
//      p和q都在root的左子树当中一>最近公共祖先在root的左树当中(可使用递归)
//      3、p.val > root.val && q.val > root.val
//      p和q都在root的右子树当中- >最近公共祖先在root的右树当中(可使用递归)
//      4、q.val < root.val && p.val> root.val || p.val < root.val && q.val> root.val
//      q和p分别在root的左子树和右子树当中   最近公共祖先就是root


    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//        判断root是否为空
        if (root == null) return null;
//        如果 p q 其中有一个等于根节点 那么他们的最近公共祖先就是那个根节点
        if (p == root || q == root) return root;
//        上面没满足 还剩三种情况  1.分别在两边     2.pq都在左      3.pq都在右边
//        lowestCommonAncestor查看返回值如果为空那么就不在那边
        TreeNode leftT = lowestCommonAncestor(root.left, p, q);
        TreeNode rightT = lowestCommonAncestor(root.right, p, q);
//        1.分别在两边
        if (leftT != null && rightT != null) {
            return root;
//        2.pq都在左
        } else if (leftT != null) {
            return leftT;
//        3.pq都在右边
        } else {
            return rightT;
        }
    }


//    思路二：
//      假设这棵二叉树是使用孩子双亲表示法  我们就可以把问题转化为 链表求交点
//      先分别求出pq的长度 哪个长哪个先走 然后同时走
//      可惜该题的二叉树不是使用双亲表示法    所以我们可以如何借助这种思路解题

//    我们可以
//    1.创建两个栈 分别存储 p q 的路径   （难点）
//          通过一个getPath函数  求 p q的路径
//    2.求栈的大小
//    3.让栈多的元素 先出(栈多-栈少)个元素 再同时出
//    4.直到栈顶元素相同 此时就是最近公共祖先

    /**
     * 求根节点到node的路径 存放在stack中
     * @param root 根节点
     * @param node  指定节点
     * @param stack 存放根节点到指定节点的路径
     * @return
     */
    public boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {
//        寻找的树 和 找的节点不能为空
        if (root == null || node == null) {
            return false;
        }
//        如果不为空 将根节点放入栈中
        stack.push(root);
//        如果root == node说明找到该节点了
        if (root == node) {
            return true;
        }
//        递归 从根节点的左子树开始找
        boolean flag = getPath(root.left,node,stack);
        if (flag == true) {//可以简化为flag
            return true;
        }
//        从根节点的右子树开始找
        flag = getPath(root.right,node,stack);
        if (flag) {
            return true;
        }
//        该节点的左右子树都没找到 将该节点从栈中删除
        stack.pop();
//        返回false 使上条递归语句flag == false 继续往下执行
        return false;
    }

    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
//        通过函数getPath 分别找出 p 和 q 的路径
        Stack<TreeNode> stack1 =new Stack<>();
        getPath(root, p, stack1);
        Stack<TreeNode> stack2 =new Stack<>();
        getPath(root, q, stack2);
//        求p 和 q的长度
        int size1 = stack1.size();
        int size2 = stack2.size();
        if (size1 > size2) {
//            删去stack1比stack2多的元素  使是两个栈一样长
            int size = size1 - size2;
            while (size != 0) {
                stack1.pop();
                size--;
            }
//            两个栈都不为空 比较栈顶元素 不相同 同时删除一个元素继续比较
            while (!stack1.empty() && !stack2.empty()) {
                if (stack1.peek() == stack2.peek()) {
                    return stack1.peek();
                }else {
                    stack1.pop();
                    stack2.pop();
                }
            }
            return null;
        }else {
            int size = size2 - size1;
            while (size != 0) {
                stack2.pop();
                size--;
            }

            while (!stack1.empty() && !stack2.empty()) {
                if (stack1.peek() == stack2.peek()) {
                    return stack1.peek();
                }else {
                    stack1.pop();
                    stack2.pop();
                }
            }
            return null;
        }
    }



//    JZ36 二叉搜索树与双向链表
//    输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表
//    1.要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继
//    2.返回链表中的第一个节点的指针
//    3.函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构
//    4.你不用输出双向链表，程序会根据你的返回值自动打印输出
//    思路：
//    1.排序：中序列表遍历这棵树
//    2.双向链表      left：变成双向链表的前驱  right：变成双向链表的后续
//    3.如何在中序遍历的时候 修改指向  （难点）

    TreeNode pre = null;
    public void inOrder(TreeNode root) {
        if (root == null) return;

        inOrder(root.left);

//        打印的部分(改变指向的部分  重点在这)  pre表示root的前驱节点
        root.left = pre;
        if (pre != null) {
            pre.right = root;
        }//如果没这判断条件 代码会在走到叶子节点的时候发生空指针异常
        pre = root;


        inOrder(root.right);
    }
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) return null;

        inOrder(pRootOfTree);

        TreeNode head = pRootOfTree;
//        找到双向链表头结点的位置
        while (head.left != null) {
            head = head.left;
        }
        return head;
    }





//    105. 从前序与中序遍历序列构造二叉树
//    给定两个整数数组 preorder 和 inorder ，其中
//    preorder 是二叉树的先序遍历，inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
//    思路：
//    1.先将前序遍历中的每个下标节点（pre）创建为root
//    2.在中序遍历中数组中 找到当前pre下标的元素存在的位置 middle





//    preIndex 得设置成全局变量  因为preIndex++得一直++下去  如果放入递归(createPreAndIn)里面
//    第一次找完根节点的左子树 在回退的时候 preIndex又回到0  这样我们就没法找到根节点的右子树的下标
    public int preIndex = 0;
    /**
     * 使用前序与中序遍历序列构造二叉树
     * @param preorder  前序遍历数组
     * @param inorder   中序遍历数组
     * @param left      中序遍历数组最左边元素
     * @param right     中序遍历数组最右边元素
     * @return          根节点
     */
    public TreeNode createPreAndIn(int[] preorder, int[] inorder, int left, int right) {
//        这条if语句是判断 递归是否结束 （重要）
        if (left > right) {
            return null;
        }//说明没有左子树 或者右子树

//        如果前序遍历数组或者中序遍历数组 其中一个为空
        if (preorder == null || inorder == null) return null;

//        root存放根节点
        TreeNode root = new TreeNode(preorder[preIndex]);
        int middle = findInorderValue(inorder, left, right, root.val);
        if (middle == -1) {
            return null;
        }
        preIndex++;

//      递归 分别创建左子树和右子树
        root.left = createPreAndIn(preorder, inorder, left, middle-1);
        root.right = createPreAndIn(preorder, inorder, middle+1, right);
        return root;
    }

    /**
     * 找到前序遍历中的根 在中序遍历数组下标什么位置
     * @param inorder  中序遍历数组
     * @param left      最左边元素
     * @param right     最右边元素
     * @param val       需要寻找的值
     * @return
     */
    public int findInorderValue(int[] inorder, int left, int right, int val) {
//        i需要<= 因为在传入right的时候已经-1了
        for (int i = left; i <= right ; i++) {
//            如果找到返回下标
            if (inorder[i] == val){
                return i;
            }
        }
//        没找到返回-1
        return -1;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null) return null;
        return createPreAndIn(preorder, inorder,0,inorder.length-1);
    }




//    106. 从中序与后序遍历序列构造二叉树
//    给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历，
//    postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
public int postIndex = 0;//成员变量 可以在buildTree中赋值
    public TreeNode createInAndPost(int[] inorder, int[] postorder, int left, int right) {
        if (left > right) {
            return null;
        }
        if (postorder == null || inorder == null) return null;
        TreeNode root = new TreeNode(postorder[postIndex]);
        int middle = findInorderValue2(inorder, left, right, root.val);
        if (middle == -1) {
            return null;
        }
        postIndex--;
        root.right = createInAndPost(inorder, postorder, middle+1, right);
        root.left = createInAndPost(inorder, postorder, left, middle-1);
        return root;
    }
    public int findInorderValue2(int[] inorder, int left, int right, int val) {
        for (int i = left; i <= right ; i++) {
            if (inorder[i] == val){
                return i;
            }
        }
        return -1;
    }
    public TreeNode buildTree2(int[] inorder, int[] postorder) {
        if (inorder == null || postorder == null) return null;
        postIndex = postorder.length-1;
        return createInAndPost(inorder, postorder,0,inorder.length-1);
    }






//    606. 根据二叉树创建字符串  看图理解  https://leetcode.cn/problems/construct-string-from-binary-tree/
//    给你二叉树的根节点 root ，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。
//    空节点使用一对空括号对 "()" 表示，转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。
//    看图理解吧

    public void treeToString(TreeNode root, StringBuilder sb) {
        if (root == null) return;
//        sb传入根的值
        sb.append(root.val);
        if (root.left != null) {
            sb.append("(");
            treeToString(root.left,sb);
            sb.append(")");
        }else {//root.left == null
            if (root.right == null) {
                return;
            }else {//root.right != null
                sb.append("()");
            }
        }

        if (root.right != null) {
            sb.append("(");
            treeToString(root.right,sb);
            sb.append(")");
        }else {//root.right == null
            return;
        }
    }
    public String tree2str(TreeNode root) {
        if (root == null) return null;
//        StringBuilder字符串拼接
        StringBuilder sb = new StringBuilder();
        treeToString(root,sb);
        return sb.toString();
    }
}
